package base.C06_BinarySearch;

/**
 * Instruction：二分法查找: 递归实现.
 * Author：@author MaLi
 */
public class Code02_BinarySearch {
    //定义一个查找方法
    public int find(int[] arr, int num) {
        //有效性验证
        if (arr == null || arr.length < 1) {
            return -1;
        }
        int start = 0;
        int end = arr.length - 1;
        return recursionFind(arr, num, start, end);
    }

    public int recursionFind(int[] arr, int num, int start, int end) {
        //使用递归模式实现
        int middle;
        middle = start + ((end - start) >> 1);
        if (arr[middle] == num) {
            return middle;
        } else if (arr[middle] > num) {
            return recursionFind(arr, num, start, middle - 1);//说明中间值在目标值的右边, 我们应该重新确定end值, 排除一半无用值
        } else if (arr[middle] > num) {
            return recursionFind(arr, num, middle + 1, end);//说明中间值在目标值的左边, 我们应该重新确定start值, 排除一半无用值
        } else {
            return -1;
        }
    }
}
